During normal use of electronic data processing equipment electronic memory which has been used is freed for reuse. Such blocks of memory typically are of a wide variation of sizes and in a wide variation of locations. Although patterns of sizes for such returned memory and their locations can be predicted broadly for individual applications, this information is far from being precise enough for direct use to once again use the returned memory.
Prior to this invention such returned memory has been sorted by some category, such as by size or by order of addresses, and located for reuse by searching through such a sort. U.S. Pat. No. 5,109,336 to Guenther et al discloses such retrieval of memory. In this patent blocks of memory of different, predetermined sizes are disclosed as allocated by the program being executed. Returned memory of such sizes are added to these allocations. Where the allocated memory is not used, all other returned memory is searched in the order in which it has been sorted. This invention does not employ such allocated blocks of memory and limits the search through sorted returned memory in a manner to be described below.
This invention employs address pointers to achieve improved retrieval of returned memory. The use of such pointers per se is widely conventional. U.S. Pat. No. 4,807,120 to Courts discloses the use of pointers in a system not particularly similar to this invention except that it is for memory management with respect to returned memory.
The preferred embodiment of this invention categorizes returned memory according to sizes which vary by a single integer of powers of 2. The "gmalloc" code of a public UNIX (trademark) source code listing allocates memory to block differing by such powers of 2. However, these allocations are not related to returned memory in any manner similar to this invention since the allocations do not involve memory returned after the allocations.
Contemporary computer design employs a working memory space generally referred to as the "heap" or "free memory." The memory manager function of the data processor is given control of this typically large memory space, and it responds to program requests for memory blocks by identifying or creating an appropriate block and giving control of it to the requester in a process known as allocation. When the active program is done with a given memory block, a process known as "freeing," it relinquishes control of it to the memory manager. The memory manager will then store the block in some form from which it can be retrieved for other use in the same or different program at a later time.
Traditionally, memory managers must sacrifice memory usage efficiency for performance. Since the performance cost of sorting memory blocks in those systems is too great, comprehensive searches or intelligent allocation strategies are not practical. Subsequently, their searches will often encounter numerous blocks that are too small to be useful, forcing the program designer to either carve the desired size off of the first free block encountered that is large enough to fill the request or use a limited number of allowed block sizes and waste the difference between the size needed and the size provided. Although this approach is generally successful in systems with a low to moderate memory utilization ratio, systems requiring higher memory utilization cannot afford the waste. In these environments, such systems can expend significant search effort and may exhibit undesirable fragmentation patterns leading to premature "memory full" conditions. When fragmentation becomes severe, it is not uncommon for "out of memory" failures to occur even though 10 times the requested memory or more is available.
This invention requires more initial computational overhead than simple, unordered systems, but quickly makes up the deficit in searches involving more than a very few returned memory blocks. Further, its unique approach is designed to allow elaborate allocation strategies and other memory enhancements that were otherwise performance prohibitive in memory systems suffering from "fragmentation."